package algorithm.segmentTree;

public class MySegmentTree {

    //适用范围：对一个范围/区间内的数据进行修改和查询，可以根据左侧和右侧信息简单整合，无需进一步调研就可以得到父节点的值

    //如果在当前节点表示的范围中可以懒住，就无需下放。
    //时间复杂度2logN,即范围的两个边界,O(logN)
    public static class SegmentTree{
        private int MaxN;
        private int[] arr;
        private int[] sum;
        private int[] lazy; //用于范围上的求和需求,记录某一个位置求和操作没有下放的数据
        private int[] change;//记录某一个位置更新操作没有下放的数据
        private boolean[] update;

        private int l;
        private int r;


        public SegmentTree(int[] origin){
            int num = origin.length + 1;
            MaxN = num;
            arr = new int[MaxN];
            for (int i = 1; i < num; i++) {
                arr[i] = origin[i - 1];
            }
            sum = new int[MaxN << 2];
            lazy = new int[MaxN << 2];
            change = new int[MaxN << 2];
            update = new boolean[MaxN << 2];
            l = 1;
            r = origin.length;
        }

        private void pushUp(int rt){
            sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
        }

        //rt：下标位置， l, r:下标位置对应的范围
        public void build(int l, int r, int rt){
            if(l == r){
                sum[rt] = arr[l];
                return;
            }
            int mid = (l + r) >> 1;
            build(l, mid, rt << 1);
            build(mid + 1, r, rt << 1 | 1);
//            sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
            pushUp(rt);
        }

        private void pushDown(int rt, int ln, int rn){
            if(update[rt]){
                update[rt << 1] = true;
                update[rt << 1 | 1] = true;
                change[rt << 1] = change[rt];
                change[rt << 1 | 1] = change[rt];
                sum[rt << 1] = ln * change[rt];
                sum[rt << 1 | 1] = rn * change[rt];
                lazy[rt << 1] = 0;
                lazy[rt << 1 | 1] = 0;
                update[rt] = false; //当前节点的update已经下放完毕
            }
            if(lazy[rt] != 0){
                lazy[rt << 1] += lazy[rt];
                lazy[rt << 1 | 1] += lazy[rt];
                sum[rt << 1] += lazy[rt] * ln;
                sum[rt << 1 | 1] += lazy[rt] * rn;
                lazy[rt] = 0;//当前节点的add已经下放完毕
            }
        }

        public void add (int L, int R, int C){
            addProcess(L, R, C, this.l, this.r, 1);
        }

        //L, R, C 业务上的参数
        //rt：下标位置， l, r:下标位置对应的范围
        private void addProcess(int L, int R, int C, int l, int r, int rt){
            //当前位置的范围被全包了，可以懒住了
            if(L <= l && R >= r){
                sum[rt] += C * (r - l + 1);
                lazy[rt] += C;
                return;
            }

            int mid = (l + r) >> 1;
            pushDown(rt, mid - l + 1, r - mid);
            if(L <= mid){
                addProcess(L, R, C, l, mid, rt << 1);
            }
            if(R > mid){
                addProcess(L, R, C, mid + 1, r, rt << 1 | 1);
            }
            pushUp(rt);
        }

        public void update(int L, int R, int C){
            updateProcess(L, R, C, this.l, this.r, 1);
        }

        private void updateProcess(int L, int R, int C, int l, int r, int rt){
            if(L <= l && R >= r){
                this.change[rt] = C;
                this.update[rt] = true;
                this.lazy[rt] = 0;
                this.sum[rt] = C * (r - l + 1);
                return;
            }

            int mid = (l + r) >> 1;
            pushDown(rt, mid - l + 1, r - mid);
            if(L <= mid){
                updateProcess(L, R, C, l, mid, rt << 1);
            }
            if(R > mid){
                updateProcess(L, R, C, mid + 1, r, rt << 1 | 1);
            }
            pushUp(rt);
        }

        public int query(int L, int R){
            return queryProcess(L, R, this.l, this.r, 1);
        }

        public int queryProcess(int L, int R, int l, int r, int rt){
            if(L <= l && R >= r){
                return sum[rt];
            }
            int mid = (l + r) >> 1;
            pushDown(rt, mid - l + 1, r - mid);
            int ans = 0;
            if(L <= mid)
                ans += queryProcess(L, R, l, mid, rt << 1);
            if(R > mid)
                ans += queryProcess(L, R, mid + 1, r, rt << 1 | 1);
            return ans;
        }


    }


    public static void main(String[] args) {
        int[] arr = {5, 4, 6, 0, 2, 1, 8};
        SegmentTree segmentTree = new SegmentTree(arr);
        segmentTree.build(1, arr.length, 1);
        segmentTree.add(2, 6, 1);
        segmentTree.update(2, 6, 2);
        segmentTree.add(2, 6, 2);
//        segmentTree.update(2, 6, 4);
        int query = segmentTree.query(2, 7);

        System.out.println(query);
    }
}
